package top.ivansong92.example.leetcode.learning.data.struct.array;


import org.junit.Test;
import top.ivansong92.example.leetcode.learning.data.struct.array.sort.ArraySort;
import top.ivansong92.example.leetcode.learning.data.struct.array.sort.BubbleSort;

import java.util.*;
import java.util.stream.Collectors;

public class TestExample2 {

    @Test
    public void test1() {
        //System.out.println(removeDuplicates(new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3}));
        System.out.println('z'-'A');
    }

    /**
     * 80. 删除有序数组中的重复项 II
     *
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int len = nums.length;
        if (len == 1) {
            return len;
        }
        int k = 0;
        int counter = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] != nums[k]) {
                k++;
                nums[k] = nums[i];
                counter = 1;
            } else if (counter < 2) {
                k++;
                nums[k] = nums[i];
                counter++;
            } else {
                counter++;
            }
        }
        return k + 1;
    }

    /**
     * 88. 合并两个有序数组
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) {
            return;
        }
        if (m == 0) {
            if (n >= 0) {
                System.arraycopy(nums2, 0, nums1, 0, n);
            }
            return;
        }
        int[] tmp = new int[m + n];
        int index = 0;
        int left = 0, right = 0;
        while (left < m && right < n) {
            if (nums1[left] <= nums2[right]) {
                tmp[index++] = nums1[left++];
            } else {
                tmp[index++] = nums2[right++];
            }
        }

        while (left < m) {
            tmp[index++] = nums1[left++];
        }

        while (right < n) {
            tmp[index++] = nums2[right++];
        }

        if (m + n >= 0) {
            System.arraycopy(tmp, 0, nums1, 0, m + n);
        }
    }

    @Test
    public void testreverseVowels() {
        System.out.println(reverseVowels("leetcode"));
    }


    /**
     * 345. 反转字符串中的元音字母
     * @param s
     * @return
     */
    public String reverseVowels(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int len = s.length();
        char[] chars = s.toCharArray();
        char[] newChars = new char[len];
        int start = 0, end = len - 1;
        while (start <= end) {
            char s1 = chars[start];
            char s2 = chars[end];
            if (!vowels.contains(s1) && !vowels.contains(s2)) {
                newChars[start] = s1;
                newChars[end] = s2;
                start ++;
                end --;
            } else if (!vowels.contains(s1)) {
                newChars[start] = s1;
                start ++;
            } else if (!vowels.contains(s2)) {
                newChars[end] = s2;
                end --;
            } else {
                newChars[start] = s2;
                newChars[end] = s1;
                start ++;
                end --;
            }
        }
        return new String(newChars);
    }

    private static Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));


    /**
     * 11. 盛最多水的容器
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }

        int res = 0;
        int i = 0, j = height.length - 1;
        while (i < j) {
            int hi = height[i];
            int hj = height[j];
            if (hi > hj) {
                res = Math.max(res, (j - i) * hj);
                j --;
            } else {
                res = Math.max(res, (j - i) * hi);
                i ++;
            }
        }

        return res;
    }


    /**
     * 209. 长度最小的子数组
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {

        int len = nums.length;
        int start = 0, end = 0;
        int res = Integer.MAX_VALUE;
        int tmp = 0;
        while (end < len) {
            if (start == end) {
                if (nums[end] >= target) {
                    return 0;
                }
                tmp = nums[start];
                end ++;
                continue;
            }
            if (tmp + nums[end] < target) {
                tmp += nums[end];
                end ++;
            } else {
                res = Math.min(res, end - start + 1);
                tmp -= nums[start];
                start ++;
            }

        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    /**
     * 3. 无重复字符的最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Set<Character> filter = new HashSet<>();
        int i = 0, j = 1, res = 1;
        int len = s.length();
        filter.add(s.charAt(i));
        while (j < len) {
            if (filter.contains(s.charAt(j))) {
                filter.remove(s.charAt(i));
                i ++;
            } else {
                filter.add(s.charAt(j));
                j ++;
            }
            res = Math.max(res, filter.size());
        }
        return res;
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        if (p == null || p.length() == 0 || s == null || s.length() < p.length()) {
            return Collections.emptyList();
        }

        int pLen = p.length();
        int[] pArray = new int[26];
        int[] sArray = new int[26];
        Set<Character> filter = new HashSet<>();
        for (int i = 0; i < pLen; i++) {
            int val = p.charAt(i) - 'a';
            filter.add(p.charAt(i));
            pArray[val] = pArray[val] + 1;
            val = s.charAt(i) - 'a';
            sArray[val] = sArray[val] + 1;
        }
        List<Integer> res = new ArrayList<>();
        if (match(pArray, sArray)) {
            res.add(0);
        }

        for (int i = pLen; i < s.length(); i++) {
            int p1 = s.charAt(i - pLen) - 'a';
            sArray[p1] = sArray[p1] - 1;
            char ch = s.charAt(i);
            p1 = ch - 'a';
            sArray[p1] = sArray[p1] + 1;
            if (filter.contains(ch) && match(pArray, sArray)) {
                res.add(i - pLen + 1);
            }
        }
        return res;
    }

    private boolean match(int[] array1, int[] array2) {
        if (array1.length != array2.length) {
            return false;
        }
        for (int i = 0; i < array1.length; i++) {
            if (array1[i] != array2[i]) {
                return false;
            }
        }
        return true;
    }


    /**
     * 76. 最小覆盖子串
     * https://leetcode.cn/problems/minimum-window-substring/
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        int tLen = t.length();
        int sLen = s.length();
        if (sLen < tLen) {
            return "";
        }

        if (s.contains(t)) {
            return t;
        }

        int[] sArray = new int[58];
        int[] tArray = new int[58];
        Set<Character> filter = new HashSet<>();
        for (int i = 0; i < tLen; i++) {
            char sch = s.charAt(i);
            sArray[sch - 'A']++;
            char tch = t.charAt(i);
            filter.add(tch);
            tArray[tch - 'A']++;
        }

        if (moreMatch(tArray, sArray)) {
            return s.substring(0, tLen);
        }

        int r = tLen, l = 0;
        String res = "";
        while (r <= sLen && l <= sLen - tLen) {
            char lCh = s.charAt(l);
            if (r == sLen) {
                if (filter.contains(lCh) && moreMatch(tArray, sArray)) {
                    String tmp = s.substring(l, r);
                    if (res.equals("") || res.length() > tmp.length()) {
                        res = tmp;
                    }
                }
                sArray[lCh - 'A'] --;
                l ++;
            } else {
                char rCh = s.charAt(r);
                sArray[rCh - 'A'] ++;
                if (filter.contains(rCh) && moreMatch(tArray, sArray)) {
                    String tmp = s.substring(l, r + 1);
                    if (res.equals("") || res.length() > tmp.length()) {
                        res = tmp;
                    }
                    sArray[lCh - 'A'] --;
                    sArray[rCh - 'A'] --;
                    l ++;
                } else {
                    r ++;
                }
            }
        }

        return res;
    }

    private boolean moreMatch(int[] ori, int[] aim) {
        if (ori.length != aim.length) {
            return false;
        }

        for (int i = 0; i < ori.length; i++) {
            if (ori[i] > aim[i]) {
                return false;
            }
        }

        return true;
    }
}
